﻿//using Nemerle.Collections;
using Nemerle.Text;
using Nemerle.Utility;
using Nemerle.Assertions;

using System;
using System.Collections.Generic;
using System.Linq;

using SC = System.Collections;

namespace Nemerle.Data
{
  
  type Seq[T] = IEnumerable[T];
  
  
  public interface ITraversable[T]
  {
    
    Iter(action : T -> void) : void;
    
    IterI(action : int * T -> void) : void;
  }
  
  
  public interface IFunctor[T]
  {
    
    Map[To](f : T -> To) : Seq[To];
    
    MapI[To](f : int * T -> To) : Seq[To];
  }
  
  
  public interface IFilterable[T]
  {
    
    Filter(f : T -> bool) : Seq[T];
    
    FilterI(f : int * T -> bool) : Seq[T];
    
    Find(f : T -> bool) : option[T];
  }
  
  
  public interface ILeftFoldable[T]
  {
    
    FoldLeft[TAccumulator]( 
      init : TAccumulator,
      f : TAccumulator * T -> TAccumulator
    ) : TAccumulator;
    
    
    ReduceLeft(f : T * T -> T) : T;
    
    FoldLeftI[TAccumulator]( 
      init : TAccumulator,
      f : int * TAccumulator * T -> TAccumulator
    ) : TAccumulator;
  }
  
  
  public interface IRightFoldable[T]
  {
    
    FoldRight[TAccumulator]( 
      init : TAccumulator,
      f : T * TAccumulator -> TAccumulator
    ) : TAccumulator;
    
    ReduceRight(f : T * T -> T) : T;
    
    FoldRightI[TAccumulator]( 
      init : TAccumulator,
      f : int * T * TAccumulator -> TAccumulator
    ) : TAccumulator;
  }
  
  public module Seq
  {
    //------------------
    // Conversions
    //------------------
    
    public AsSeq[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[T]
    {
      seq 
    }
    
    public ToSeq[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[T]
    {
       foreach(elem in seq) yield elem
    }
    
    public ToNList[T](
      [NotNull] this seq : Seq[T]
    ) : list[T]
    {
      | arr is array[T] => arr.ToNList()
      | _               => $[x | x in seq]
    }
    
    //-------------
    // Iterations
    //-------------
    
    /// <summary>
    /// Performs the specified action on each element of the sequence.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The sequence.</param>
    /// <param name="action">The action.</param>
    public IterSeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull]   action : T -> void
    ) : void
    {
      foreach(elem in seq) 
        action(elem) 
    }
    
    /// <summary>
    /// Performs the specified action on each element of the sequence.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr">The sequence.</param>
    /// <param name="action">The action.</param>
    /// <remarks>
    /// Call specialized functions for BCL collections and implementations
    /// of <see cref="ITraversable{T}"/>.
    /// </remarks>
    public Iter[T](
      [NotNull] this seq : Seq[T],
      [NotNull]   action : T -> void
    ) : void
    {
      match(seq) {
        | arr is array[T] => arr.Iter(action)
        | traversable is ITraversable[T] => traversable.Iter(action)
        | _ => seq.IterSeq(action)
      }
    }
    
    /// <summary>
    /// Performs the specified action on each element of the sequence 
    /// by incorporating the element's index.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="sequence">The sequence.</param>
    /// <param name="action">The action.</param>
    public IterISeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull]   action : int * T -> void
    ) : void
    {
      foreach(elem in seq with i) 
        action(i, elem) 
    }
    
    /// <summary>
    /// Performs the specified action on each element of the sequence 
    /// by incorporating the element's index.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="sequence">The sequence.</param>
    /// <param name="action">The action.</param>
    /// <remarks>
    /// Call specialized functions for BCL collections and implementations
    /// of <see cref="ITraversable{T}"/>.
    /// </remarks>
    public IterI[T](
      [NotNull] this seq : Seq[T],
      [NotNull]   action : int * T -> void
    ) : void
    {
      match(seq) {
        | arr is array[T] => arr.IterI(action)
        | traversable is ITraversable[T] => traversable.IterI(action)
        | _ => seq.IterISeq(action)
      }
    }
    
    //------------------
    // Basic functions
    //------------------
   
    
    public Empty[T]() : Seq[T]
    {
      Enumerable.Empty()
    }
    
    public Single[T](
      elem : T
    ) : Seq[T]
    {
      yield elem
    }
    
    #warning not tested
    public @+[T](
      [NotNull] left : Seq[T],
      [NotNull] right : Seq[T]
    ) : Seq[T]
    {
      //| (null, null) => Empty()
      //| (null, r)    => r
      //| (l, null)    => l
      | _            => left.Concat(right)
    }
    
    //public IsEmpty
    //public CheckLength[T](
    //  [NotNull] this source : Seq[T]
    //) : bool
    //{
      
    //}
    
    #warning not tested
    public Head[T](
      [NotNull] this source : Seq[T]
    ) : T
    //requires 
    {
      | seq is IList[T] => seq[0]
      | seq is SC.IList => seq[0] :> T
      | seq is list[T]  => seq.Head
      | _               => source.First() //to do
    }
    
    /// <summary>Returns all elements of the sequence except the first.</summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="source">The sequence.</param>
    /// <returns></returns>
    public TailSeq[T](
      [NotNull] this source : Seq[T]
    ) : Seq[T]
    {
      using (def e = source.GetEnumerator())
      {
        when (!e.MoveNext())
          throw ArgumentException("Empty seq.");
        while (e.MoveNext())
          yield e.Current;
      }
    }
    
    public Tail[T](
      [NotNull] this source : Seq[T]
    ) : Seq[T]
    {
      match(source) {
        | source is LazyIterator[T] => source.Tail()
        | _                         => source.TailSeq()
      }
    }
    
    
    #warning not tested
    public InitSeq[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[T]
    {
      using(e = seq.GetEnumerator())
      {
        unless(e.MoveNext())
          throw ArgumentException("Empty seq.");
    
        def loop() {
          def x = e.Current;
          when(e.MoveNext())
          {
            yield x;
            loop()
          }
        }
        loop()
      }    
    }
    
    /// <summary>
    /// Returns the length of a finite sequence.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="source">The sequence.</param>
    /// <returns>Length of a sequence.</returns>
    /// <remarks>
    /// <c> src.Length() == 0 </c> if <c>src == null</c>
    /// </remarks>
    #warning not tested
    public Length[T](
      this source : Seq[T]
    ) : int
    {
      | null => 0 //TODO null always equal empty sequence? 
      | seq is list[T] => seq.Length
      //TO DO: interface for measurable or finite containers
      | _ => source.Count()
    }
    
    
    #warning not tested
    public AppendSeq[T](
      [NotNull] this seq : Seq[T],
                    item : T
    ) : Seq[T]
    {
      foreach(x in seq) yield x;
      yield item;
    }
    
    
    #warning not tested
    public PrependSeq[T](
      [NotNull] this seq : Seq[T],
                    item : T
    ) : Seq[T]
    {
      yield item;
      foreach(x in seq) yield x;
    }
    
    
    #warning not tested
    public Prepend[T](
      [NotNull] this seq : Seq[T],
                    item : T
    ) : Seq[T]
    {
      match(seq) {
        | seq is LazyIterator[T] => LazyIterator.Cons(item, seq)
        | _                      => seq.PrependSeq(item) 
      }
    }
    
    //--------------------------
    // Sequence transformations
    //--------------------------
    
    /// <summary>
    /// Creates a new collection whose elements are the results of applying 
    /// the given function f to each of the elements of the collection source. 
    /// The given function will be applied as elements are demanded using the 
    /// MoveNext method on enumerators retrieved from the object.
    /// </summary>
    /// <typeparam name="From"></typeparam>
    /// <typeparam name="To">The type of the result.</typeparam>
    /// <param name="source">The sequence.</param>
    /// <param name="f">The function.</param>
    /// <returns></returns>
    public MapSeq[From, To](
      [NotNull] this source : Seq[From],
      [NotNull] f : From -> To
    ) : Seq[To]
    {
      foreach(x in source)
        yield f(x)
    }
    
    /// <summary>
    /// Creates a new collection whose elements are the results of applying 
    /// the given function f to each of the elements of the collection source. 
    /// The given function will be applied as elements are demanded using the 
    /// MoveNext method on enumerators retrieved from the object.
    /// The integer passed to the function indicates the index of element.
    /// </summary>
    /// <typeparam name="From"></typeparam>
    /// <typeparam name="To">The type of the result.</typeparam>
    /// <param name="source">The sequence.</param>
    /// <param name="f">The function.</param>
    /// <returns></returns>
    public MapISeq[From, To](
      [NotNull] this source : Seq[From],
      [NotNull] f : int * From -> To
    ) : Seq[To]
    {
      foreach(x in source with i)
        yield f(i, x)
    }
    
    
    #warning not tested
    public Rev[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[T]
    {
      def result = seq.ToArray();
      Array.Reverse(result);
      result
    }
    
    
    #warning not tested
    public IntersperseSeq[T](
      [NotNull] this seq : Seq[T], 
               separator : T
    ) : Seq[T]
    {
      using(e = seq.GetEnumerator())
      {
        def loop() {
          when(e.MoveNext())
          {
            yield separator;
            yield e.Current;
            loop()
          }
        }
        yield e.Current;
        loop()
      }
    }
    
    
    #warning not tested
    public IntersperseWithSeq[T](
      [NotNull] this seq : Seq[T], 
                     f   : T * T -> T
    ) : Seq[T]
    {
      using(e = seq.GetEnumerator())
      {
        def loop(prev) {
          when(e.MoveNext())
          {
            def x = e.Current;
            yield f(prev, x);
            yield x;
            loop(x)
          }
        }
        def x = e.Current;
        yield x;
        loop(x)
      }
    }

    
    #warning not tested
    public MapOptionSeq[From, To](
      [NotNull] this source : Seq[From],
      [NotNull] f           : From -> option[To]
    ) : Seq[To]
    {
      foreach(x in source)
      {
        def res = f(x);
        when(res.IsSome) yield res.Value;
      }
    }
    
    
    #warning not tested
    public CatOptionsSeq[T](
      [NotNull] this source : Seq[option[T]]
    ) : Seq[T]
    {
      foreach(Some(x) in source) yield x
    }
    
    
    #warning not tested
    public PairwiseWithSeq[From, To](
      [NotNull] this source : Seq[From],
      [NotNull] f           : From * From -> To
    ) : Seq[To]
    {
      using(e = source.GetEnumerator())
      {
        def loop(prev) {
          when(e.MoveNext())
          {
            def x = e.Current;
            yield f(prev, x);
            loop(x)
          }
        }
        loop(e.Current)
      }
    }
    
    
    
    #warning not tested
    public PairwiseSeq[T](
      [NotNull] this source : Seq[T],
    ) : Seq[T * T]
    {
      using(e = source.GetEnumerator())
      {
        def loop(prev) {
          when(e.MoveNext())
          {
            def x = e.Current;
            yield (prev, x);
            loop(x)
          }
        }
        loop(e.Current)
      }
    }
    
    
    #warning not tested
    public ReducePairs[From, To](
      [NotNull] this source : Seq[From],
      [NotNull] f           : From * From -> To
    ) : Seq[To]
    {
      using(e = source.GetEnumerator())
      {
        def loop(prev) {
          when(e.MoveNext())
          {
            yield f(prev, e.Current);
            when(e.MoveNext())
              loop(e.Current)
          }
        }
        loop(e.Current)
      }
    }
    
    //-----------------------------
    // Reducing sequences (folds)
    //-----------------------------
    
    /// <summary>
    /// Reduces the sequence source from left to right using the specified 
    /// binary function f starting with the specified accumulator value init.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="sequence">The sequence to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The final accumulator value.</returns>
    /// <remarks>
    /// An alternate name for <see cref="Enumerable.Aggregate{TSource,TAccumulate}"/>.
    /// </remarks>
    public FoldSeq[TAccumulator, T](
      [NotNull] this sequence : Seq[T],
      mutable   acc           : TAccumulator,
      [NotNull] f             : TAccumulator * T -> TAccumulator
    ) : TAccumulator
    {
      foreach (value in sequence)
        acc = f(acc, value);
      acc
    }
    
    /// <summary>
    /// Reduces the sequence source from left to right using the specified 
    /// binary function f starting with the specified accumulator value init.
    /// The integer passed to the function indicates the index of element.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="sequence">The sequence to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The final accumulator value.</returns>
    /// <remarks>
    /// An alternate name for <see cref="Enumerable.Aggregate{TSource,TAccumulate}"/>.
    /// </remarks>
    public FoldISeq[TAccumulator, T](
      [NotNull] this sequence : Seq[T],
      mutable   acc           : TAccumulator,
      [NotNull] f             : int * TAccumulator * T -> TAccumulator
    ) : TAccumulator
    {
      foreach (value in sequence with i)
        acc = f(i, acc, value);
      acc
    }
    
    /// <summary>
    /// Reduces the container source from left to right using the specified 
    /// binary function f starting with the specified accumulator value init.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="sequence">The sequence to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="init">The initial value of the accumulator.</param>
    /// <returns>The final accumulator value.</returns>
    /// <remarks>
    /// Call specialized functions for BCL collections and implementations
    /// of <see cref="ILeftFoldable{T}"/>.
    /// </remarks>
    #warning not tested
    public Fold[TAccumulator, T](
      [NotNull] this sequence : Seq[T],
                     init     : TAccumulator,
      [NotNull]      f        : TAccumulator * T -> TAccumulator
    ) : TAccumulator
    {
      match (sequence) {
        | arr is array[T] => arr.Fold(init, f)
        | foldable is ILeftFoldable[T] => foldable.FoldLeft(init, f)
        | _ => sequence.FoldSeq(init, f)
      }
    }
    
    /// <summary>
    /// Reduces the sequence from left to right using the specified binary function and
    /// starting with the first element of the sequence.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <param name="sequence">The sequence to fold.</param>
    /// <param name="func">The binary function.</param>
    /// <returns>The final accumulator value.</returns>
    /// <remarks>
    /// An alternate name for <see cref="Enumerable.Aggregate{TSource}"/>.
    /// </remarks>
    public ReduceSeq[T](
      [NotNull] this sequence : Seq[T],
      [NotNull]      f        : T * T -> T
    ) : T
    {
      sequence.TailSeq().FoldSeq(sequence.Head(), f)
    }
    
    /// <summary>
    /// Reduces the sequence from left to right using the specified binary function and
    /// starting with the first element of the sequence.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <param name="sequence">The sequence to fold.</param>
    /// <param name="func">The binary function.</param>
    /// <returns>The final accumulator value.</returns>
    /// <remarks>
    /// Call specialized functions for BCL collections and implementations
    /// of <see cref="ILeftFoldable{T}"/>.
    /// </remarks>
    #warning not tested
    public Reduce[T](
      [NotNull] this sequence : Seq[T],
      [NotNull] f : T * T -> T
    ) : T
    {
      match(sequence) {
        | arr is array[T] => arr.Reduce(f)
        | foldable is ILeftFoldable[T] => foldable.ReduceLeft(f)
        | _ => sequence.ReduceSeq(f)
      }
    }
    
    //----------------
    // Special folds
    //----------------
    
    //Flatten?
    
    public ConcatenateSeq[T, TSeq](
      [NotNull] this seqs : Seq[TSeq],
    ) : Seq[T]
    where TSeq : Seq[T]
    {
      foreach(seq in seqs)
        foreach(elem in seq)
          yield elem
    }
    
    #warning Not Tested
    public ConcatenateSeq[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
    ) : Seq[T]
    {
      foreach(elem in seq1) yield elem;
      foreach(elem in seq2) yield elem;
    }
    
    /// <summary>
    /// Map a function over a sequence and concatenate the results.
    /// The given function will be applied as elements are demanded using the 
    /// MoveNext method on enumerators retrieved from the object.
    /// </summary>
    /// <typeparam name="From"></typeparam>
    /// <typeparam name="To">The type of the result.</typeparam>
    /// <param name="source">The sequence.</param>
    /// <param name="f">The function.</param>
    /// <returns></returns>
    public ConcatMapSeq[From, To](
      [NotNull] this seq : Seq[From],
      [NotNull] f        : From -> Seq[To]
    ) : Seq[To]
    {
      foreach(x in seq)
        foreach(y in f(x))
          yield y
    }
    
    public ExistSeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull] f        : T -> bool
    ) : bool
    {
      exit : {
       foreach(elem in seq)
         when(f(elem)) exit(true);
       false
      }
    }
    
    
    public ForAllSeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull] f        : T -> bool
    ) : bool
    {
      exit : {
       foreach(elem in seq)
         unless(f(elem)) exit(false);
       true
      }
    }
    
    /// <summary>
    /// Returns the disjunction of a sequence of <see cref="bool"/>s.
    /// </summary>
    /// <param name="bools">The sequence of booleans.</param>
    /// <returns>The disjunction.</returns>
    public OrSeq(
      [NotNull] this seq : Seq[bool],
    ) : bool
    {
      exit : {
       foreach(elem in seq)
         when(elem) exit(true);
       false
      }
    }
    
    /// <summary>
    /// Returns the conjunction of a sequence of <see cref="bool"/>s.
    /// </summary>
    /// <param name="bools">The sequence of booleans.</param>
    /// <returns>The conjunction.</returns>
    public AndSeq(
      [NotNull] this seq : Seq[bool],
    ) : bool
    {
      exit : {
       foreach(elem in seq)
         unless(elem) exit(false);
       true
      }
    }
    
    
    #warning not tested
    public MaximumSeq[T](
      [NotNull] this seq : Seq[T]
    ) : T
    where T : IComparable[T]
    {
      using(e = seq.GetEnumerator())
      {
        def loop(max) {
          if(e.MoveNext())
          {
            def x = e.Current;
            if(x.CompareTo(max) > 0) loop(x) else loop(max) 
          }
          else
            max
        }
        unless(e.MoveNext()) throw ArgumentException("Empty seq.");
        loop(e.Current)
      }
    }
    
    
    #warning not tested
    public MaximumBySeq[T, K](
      [NotNull] this seq : Seq[T],
      [NotNull] selector : T -> K
    ) : T
    where K : IComparable[K]
    {
      using(e = seq.GetEnumerator())
      {
        def loop(max, key) {
          if(e.MoveNext())
          {
            def x = e.Current;
            def xk = selector(x);
            if(xk.CompareTo(key) > 0) loop(x, xk) else loop(max, key) 
          }
          else
            max
        }
        unless(e.MoveNext()) throw ArgumentException("Empty seq.");
        def x = e.Current;
        loop(x, selector(x))
      }
    }
    
    
    #warning not tested
    public MaximumsBySeq[T, K](
      [NotNull] this seq : Seq[T],
      [NotNull] selector : T -> K
    ) : Seq[T]
    where K : IComparable[K]
    {
      using(e = seq.GetEnumerator())
      {
        def res = List();
        def loop(max, key) {
          when(e.MoveNext())
          {
            def x = e.Current;
            def xk = selector(x);
            def cmp = xk.CompareTo(key);
            when(cmp > 0) res.Clear();
            unless(cmp < 0)
            {
              res.Add(x); 
              loop(x, xk)
            }
            loop(max, key)
          }
        }
        unless(e.MoveNext()) throw ArgumentException("Empty seq.");
        def x = e.Current;
        loop(x, selector(x));
        res
      }
    }
    
    
    #warning not tested
    public MinimumSeq[T](
      [NotNull] this seq : Seq[T]
    ) : T
    where T : IComparable[T]
    {
      using(e = seq.GetEnumerator())
      {
        def loop(min) {
          if(e.MoveNext())
          {
            def x = e.Current;
            if(x.CompareTo(min) < 0) loop(x) else loop(min) 
          }
          else
            min
        }
        unless(e.MoveNext()) throw ArgumentException("Empty seq.");
        loop(e.Current)
      }
    }
    
    
    #warning not tested
    public MinimumBySeq[T, K](
      [NotNull] this seq : Seq[T],
      [NotNull] selector : T -> K
    ) : T
    where K : IComparable[K]
    {
      using(e = seq.GetEnumerator())
      {
        def loop(min, key) {
          if(e.MoveNext())
          {
            def x = e.Current;
            def xk = selector(x);
            if(xk.CompareTo(key) < 0) loop(x, xk) else loop(min, key) 
          }
          else
            min
        }
        unless(e.MoveNext()) throw ArgumentException("Empty seq.");
        def x = e.Current;
        loop(x, selector(x))
      }
    }
    
    
    #warning not tested
    public MinimumsBySeq[T, K](
      [NotNull] this seq : Seq[T],
      [NotNull] selector : T -> K
    ) : Seq[T]
    where K : IComparable[K]
    {
      using(e = seq.GetEnumerator())
      {
        def res = List();
        def loop(min, key) {
          when(e.MoveNext())
          {
            def x = e.Current;
            def xk = selector(x);
            def cmp = xk.CompareTo(key);
            when(cmp < 0) res.Clear();
            unless(cmp > 0)
            {
              res.Add(x); 
              loop(x, xk)
            }
            loop(min, key)
          }
        }
        unless(e.MoveNext()) throw ArgumentException("Empty seq.");
        def x = e.Current;
        loop(x, selector(x));
        res
      }
    }
    
    //=================
    // Building lists
    //=================
    //--------
    // Scans
    //--------
    
    /// <summary>
    /// Reduces the sequence from left to right using the specified binary function
    /// starting with the specified accumulator value, and return the sequence of 
    /// intermediate accumulator values.
    /// </summary>
    /// <typeparam name="T">The type of the elements in the sequence.</typeparam>
    /// <typeparam name="TAccumulator">The type of the accumulator.</typeparam>
    /// <param name="seq">The sequence to fold.</param>
    /// <param name="f">The binary function.</param>
    /// <param name="acc">The initial value of the accumulator.</param>
    /// <returns>The sequence of accumulator values.</returns>
    public ScanSeq[TAccumulator, T](
      [NotNull] this seq : Seq[T],
      mutable   acc      : TAccumulator,
      [NotNull] f        : TAccumulator * T -> TAccumulator
    ) : Seq[TAccumulator]
    {
      yield acc;
      foreach (value in seq)
      {
        acc = f(acc, value);
        yield acc;
      }
    }
    
    //--------------------
    // Accumulating maps
    //--------------------
    
    //--------------------
    // Infinite iterators
    //--------------------
    
    
    #warning not tested
    public To(this start : int, stop : int) : Seq[int]
    {
      foreach(i in [start .. stop-1]) yield i
    }
    
    
    #warning not tested
    public ToInf(this start : int) : Seq[int]
    {
      def loop(i) {
        yield i;
        loop(i + 1)
      }
      loop(start)
    }
    
    
    #warning not tested
    public Times(this times : int, action : void -> void) : void
    {
      repeat(times) action()
    }
    
    //--------------------
    // Accumulating maps
    //--------------------
    
    
    #warning not tested
    public MapAccSeq[TAcc, T, R](
      [NotNull] this seq : Seq[T],
      mutable        acc : TAcc,
      [NotNull]      f   : (TAcc * T) -> (TAcc * R)
    ) : Seq[R]
    {
      foreach(item in seq with i)
      {
        def (acc', res) = f(acc, item);
        acc = acc';
        yield res;
      }
    }
    
    //------------
    // Unfolding
    //------------
    
    
    public Replicate[T](item : T, times : int) : Seq[T]
    {
      when(times > 0)
        repeat(times) yield item;
    }
    
    /// <summary>
    /// Produces a sequence from the given seed using the specified function.
    /// Function should return <c>None</c> in order to finish constructing the sequence;
    /// if <paramref name="f"/> returns a pair <c>x, state</c>, then <c>x</c> is added to the list
    /// and <paramref name="func"/> will next be called with <c>state</c> as its argument.
    /// </summary>
    /// <typeparam name="T">The type of the elements of the sequence.</typeparam>
    /// <typeparam name="TState">The type of the state.</typeparam>
    /// <param name="f">The function.</param>
    /// <param name="init">The initial state.</param>
    /// <returns></returns>
    public Unfold[TState, T](
      mutable   init : TState,
      [NotNull] f    : TState -> option[TState * T]
    ) : Seq[T]
    {
      def loop(state)
      { 
        | Some((s, r)) => {
            yield r;
            loop(f(s))
          }
        | None => ()
      }
      loop(f(init));
    }
    
    #warning no test
    
    public UnfoldInf[TState, T](
      mutable   init : TState,
      [NotNull] f    : TState -> TState*T
    ) : Seq[T]
    {
      def loop(s, r)
      { 
        yield r;
        loop(f(s))
      }
      loop(f(init));
    }
    
    //===============
    // Subsequences
    //===============
    //--------------------------
    // Extracting subsequences
    //--------------------------
    
    public TakeExactlySeq[T](
      [NotNull] this seq : Seq[T],
                       n : int
    ) : Seq[T]
    requires n >= 0
    {
      using(e = seq.GetEnumerator())
      repeat(n)
        if (e.MoveNext()) 
          yield e.Current
        else
          throw ArgumentException()
    }
    
    
    public DropExactly[T](
      [NotNull] this e : IEnumerator[T],
                       n : int
    ) : void
    {
        repeat(n)
          unless (e.MoveNext()) 
            throw ArgumentException();
    }
    
    
    public ToSeq[T](
      [NotNull] this e : IEnumerator[T]
    ) : Seq[T]
    {
      while(e.MoveNext())
        yield e.Current
    }
    
    public DropExactlySeq[T](
      [NotNull] this seq : Seq[T],
                       n : int
    ) : Seq[T]
    { 
      if(n == 0)
        seq
      else using(e = seq.GetEnumerator())
      {
        e.DropExactly(n);
        e.ToSeq()
      }
    }
    
    //#warning not tested
    //
    //public OrganizeSeq[T](
    //  [NotNull] this seq : Seq[T]
    //) : Seq[Seq[T]]
    //{
    //  def cmp = EqualityComparer.Default;
    //  using(e = seq.GetEnumerator())
    //  while(e.MoveNext())
    //    yield TakeEqualsSeq(e, cmp);
    //}
    
    //private TakeEqualsSeq[T](e : IEnumerator[T], cmp : EqualityComparer[T]) : Seq[T]
    //{
    //  def c = e.Current;
    //  yield c;
    //  exit : {
    //    foreach(x in EnumeratorToEnumerable(e))
    //      if(cmp.Equals(x,c)) yield x else exit()
    //  }
    //}
    
    //#warning not tested
    //
    //public OrganizeBySeq[T, K](
    //  [NotNull] this seq : Seq[T],
    //  [NotNull] selector : T -> K
    //) : Seq[K * Seq[T]]
    //{
    //  def takeEqualsSeq(e)
    //  {
    //    def c = e.Current;
    //    def key = selector(c);
    //    def res = List();
    //    res.Add(c);
    //    exit : {
    //      foreach(x in EnumeratorToEnumerable(e))
    //        if(x.Equals(c)) res.Add(x) else exit()
    //    }
    //    (key, res.ToArray())
    //  }
    //  using(e = seq.GetEnumerator())
    //  while(e.MoveNext())
    //    yield takeEqualsSeq(e);
    //}
    
    //private TakeEqualsSeq[T](e : IEnumerator[T], cmp : EqualityComparer[T]) : Seq[T]
    //{
    //  def c = e.Current;
    //  yield c;
    //  exit : {
    //    foreach(x in EnumeratorToEnumerable(e))
    //      if(cmp.Equals(x,c)) yield x else exit()
    //  }
    //}
    
    #warning not tested
    
    public Categorize[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[Seq[T]]
    {
      def dict = Dictionary();
      def keysByOrder = List();
      foreach(x in seq)
      {
        if(dict.ContainsKey(x))
        {
          dict[x].Add(x)
        }
        else
        {
          keysByOrder.Add(x);
          def category = List();
          category.Add(x);
          dict.Add(x, category);
        }
      }
      def result = array(keysByOrder.Count);
      foreach(key in keysByOrder with i)
        result[i] = dict[key] : Seq[T];
      result
    }
    
    #warning not tested
    
    public CategorizeBy[T, K](
      [NotNull] this seq : Seq[T],
      [NotNull] selector : T -> K
    ) : Seq[K * Seq[T]]
    {
      def dict = Dictionary();
      def keysByOrder = List();
      foreach(x in seq)
      {
        def key = selector(x);
        if(dict.ContainsKey(key))
        {
          dict[key].Add(x)
        }
        else
        {
          keysByOrder.Add(key);
          def category = List();
          category.Add(x);
          dict.Add(key, category);
        }
      }
      def result = array(keysByOrder.Count);
      foreach(key in keysByOrder with i)
        result[i] = (key, dict[key] : Seq[T]);
      result
    }
    
    //-------------
    // Predicates
    //-------------
    
    #warning not tested
    
    public SequenceEqSeq[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
    ) : bool
    {
      using(e1 = seq1.GetEnumerator())
      using(e2 = seq2.GetEnumerator())
      {
        def loop(_) {
          | (true, true) when e1.Current.Equals(e2.Current) => loop(e1.MoveNext(), e2.MoveNext()) 
          | (false, false)                                  => true
          | _                                               => false
        }
        loop(e1.MoveNext(), e2.MoveNext())
      }
    }
    
    #warning not tested
    
    public SetEqSeq[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
    ) : bool
    {
      def set = HashSet(seq1);
      set.SetEquals(seq2)
    }
    
    #warning not tested
    
    public IsPrefixOfSeq[T](
      [NotNull] this prefix : Seq[T],
      [NotNull]         seq : Seq[T]
    ) : bool
    {
      using(e1 = prefix.GetEnumerator())
      using(e2 = seq.GetEnumerator())
      {
        def loop(_) {
          | (true, true) when e1.Current.Equals(e2.Current) => loop(e1.MoveNext(), e2.MoveNext()) 
          | (false, _)                                      => true
          | _                                               => false
        }
        loop(e1.MoveNext(), e2.MoveNext())
      }
    }
    
    #warning not tested
    
    public IsInfixOf[T](
      [NotNull] this infix : Seq[T],
      [NotNull]        seq : Seq[T]
    ) : bool
    {
      infix.ToArray().IsInfixOf(seq.ToArray())
    }
    
    #warning not tested
    
    public IsSuffixOf[T](
      [NotNull] this suffix : Seq[T],
      [NotNull]         seq : Seq[T]
    ) : bool
    {
      suffix.ToArray().IsSuffixOf(seq.ToArray())
    }
        
    //==================
    // Searching lists
    //==================
    //------------------------
    // Searching by equality
    //------------------------
    
    public ContainsElemSeq[T](
      [NotNull] this seq : Seq[T],
                    elem : T
    ) : bool
    where T : IEquatable[T]
    {
      exit : {
       foreach(x in seq)
         when(x.Equals(elem)) exit(true);
       false
      }
    }
    
    //----------------------------
    // Searching with a predicate
    //----------------------------
    
    public FindSeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull]     pred : T -> bool
    ) : option[T]
    where T : IEquatable[T]
    {
      exit : {
       foreach(x in seq)
         when(pred(x)) exit(Some(x));
       None()
      }
    }
    
    /// <summary>
    /// Filters a sequence of values based on a predicate.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seq">The sequence.</param>
    /// <param name="pred">The predicate.</param>
    /// <returns></returns>
    public FilterSeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull]     pred : T -> bool
    ) : Seq[T]
    {
      foreach(x when pred(x) in seq)
         yield x
    }
    
    /// <summary>
    /// Filters a sequence of values based on a predicate.
    /// The integer passed to the predicate indicates the index of element.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="seq">The sequence.</param>
    /// <param name="pred">The predicate.</param>
    /// <returns></returns>
    public FilterISeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull]     pred : int * T -> bool
    ) : Seq[T]
    {
      foreach(x when pred(i, x) in seq with i)
         yield x
    }
    
    //-----------
    // Indexing
    //-----------
    
    
    
    //----------------------------------
    // Zipping and unzipping sequences
    //----------------------------------
    
    /// <summary>
    /// Takes two sequences and a function, calls the function on corresponding pairs
    /// and returns an sequence of the results.
    /// If one sequence is short, excess elements of the longer sequence are discarded.
    /// </summary>
    /// <param name="f">The function used to combine pairs.</param>
    /// <param name="seq1">The first sequence.</param>
    /// <param name="seq2">The second sequence.</param>
    /// <returns></returns>
    public ZipWithSeq[From1, From2, To](
      [NotNull] this seq1 : Seq[From1],
      [NotNull]      seq2 : Seq[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : Seq[To]
    {
      using(e1 = seq1.GetEnumerator())
      using(e2 = seq2.GetEnumerator())
      while(e1.MoveNext() && e2.MoveNext())
        yield f(e1.Current, e2.Current)        
    }
    
    /// <summary>
    /// Takes two sequences and returns a sequence of corresponding pairs. 
    /// If one array is short, excess elements of the longer sequence are discarded.
    /// </summary>
    /// <typeparam name="T1">The type of the 1.</typeparam>
    /// <typeparam name="T2">The type of the 2.</typeparam>
    /// <param name="sequence1">The first sequence.</param>
    /// <param name="sequence2">The second sequence.</param>
    /// <returns></returns>
    public ZipSeq[T1, T2](
      [NotNull] this seq1 : Seq[T1],
      [NotNull]      seq2 : Seq[T2],
    ) : Seq[T1*T2]
    {
      using(e1 = seq1.GetEnumerator())
      using(e2 = seq2.GetEnumerator())
      while(e1.MoveNext() && e2.MoveNext())
        yield (e1.Current, e2.Current)        
    }
    
    /// <summary>
    /// Takes two sequences and a function, calls the function on corresponding pairs
    /// and returns an sequence of the results.
    /// </summary>
    /// <param name="f">The function used to combine pairs.</param>
    /// <param name="seq1">The first sequence.</param>
    /// <param name="seq2">The second sequence.</param>
    /// <returns></returns>
    public Map2Seq[From1, From2, To](
      [NotNull] this seq1 : Seq[From1],
      [NotNull]      seq2 : Seq[From2],
      [NotNull]         f : From1 * From2 -> To
    ) : Seq[To]
    {
      using(e1 = seq1.GetEnumerator())
      using(e2 = seq2.GetEnumerator())
      {
        def loop(b1, b2) 
        {
          |(true, true) => { 
              yield f(e1.Current, e2.Current); 
              loop(e1.MoveNext(), e2.MoveNext())
            }
          |(false, false) => ()
          | _ => throw ArgumentException()
        };
        loop(e1.MoveNext(), e2.MoveNext())
      }
    }
    
    /// <summary>
    /// Splits a sequence of pairs into a pair of sequences.
    /// </summary>
    #warning not tested
    public UnZipSeq[T1, T2](
      [NotNull] this seq : Seq[T1*T2]
    ) : Seq[T1] * Seq[T2]
    {
      (seq.FirstsSeq(), seq.SecondsSeq()) 
    }
    
    
    #warning not tested
    public FirstsSeq[T1, T2](
      [NotNull] this seq : Seq[T1*T2]
    ) : Seq[T1]
    {
      foreach((x, _) in seq) yield x
    }
    
    
    #warning not tested
    public SecondsSeq[T1, T2](
      [NotNull] this seq : Seq[T1*T2]
    ) : Seq[T2]
    {
      foreach((_, x) in seq) yield x
    }
    
    //------------------
    // "Set" operations
    //------------------
    
    
    #warning not tested
    public UniqueElements[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[T]
    {
      Essence(seq)
    }

    
    #warning not tested
    public Essence[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[T]
    {
      def set = HashSet(seq);
      set
    }

    
    #warning not tested
    public EssenceBy[T, K](
      [NotNull] this seq : Seq[T],
      [NotNull] selector : T -> K 
    ) : Seq[T]
    {
      def set = HashSet(seq, SelectEqComparer(selector));
      set
    }
    
    
    #warning not tested
    public DeleteAllSeq[T](
      [NotNull] this seq : Seq[T],
      elem : T
    ) : Seq[T]
    {
      foreach(x in seq)
        unless(elem.Equals(x))
          yield x
    }
    
    
    #warning not tested
    public DeleteFirstSeq[T](
      [NotNull] this seq : Seq[T],
      elem : T
    ) : Seq[T]
    {
      using(en = seq.GetEnumerator())
      {
        exit : {
          foreach(x in EnumeratorToEnumerable(en)) 
            if(x.Equals(elem))
              exit();
            else
              yield x;
          foreach(x in EnumeratorToEnumerable(en)) 
            yield x;
        }
      }
    }
    
    
    #warning not tested
    public DeleteFirstBySeq[T, K](
      [NotNull] this seq : Seq[T],
                     key : K,
      [NotNull] selector : T -> K
    ) : Seq[T]
    {
      using(en = seq.GetEnumerator())
      {
        exit : {
          foreach(x in EnumeratorToEnumerable(en)) 
            if(selector(x).Equals(key))
              exit();
            else
              yield x;
          foreach(x in EnumeratorToEnumerable(en)) 
            yield x;
        }
      }
    }
    
    
    #warning not tested
    public DeleteWhenSeq[T](
      [NotNull] this seq : Seq[T],
      [NotNull]     pred : T -> bool
    ) : Seq[T]
    {
      foreach(x in seq)
        unless(pred(x))
          yield x
    }
    
    
    #warning not tested
    public DeleteFirstsSeq[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T]
    ) : Seq[T]
    {
       seq1.DiffSeq(seq2)
    }
    
    
    #warning not tested
    public DiffSeq[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T]
    ) : Seq[T]
    {
       def set = HashSet(seq2);
       foreach(x when !set.Contains(x) in seq1)
         yield x
    }
    
    
    #warning not tested
    public DiffBySeq[T, K](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
      [NotNull] selector : T -> K 
    ) : Seq[T]
    {
      def set = HashSet(seq2, SelectEqComparer(selector));
      foreach(x when !set.Contains(x) in seq1)
         yield x
    }
    
    
    #warning not tested
    public DeleteFirstsBySeq[T, K](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
      [NotNull] selector : T -> K 
    ) : Seq[T]
    {
      seq1.DiffBySeq(seq2, selector)
    }
    
    
    #warning not tested
    public SetDiff[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T] 
    ) : Seq[T]
    {
      def set = HashSet(seq1);
      set.ExceptWith(seq2);
      set
    }
    
    
    #warning not tested
    public SetDiffBy[T, K](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
      [NotNull] selector : T -> K 
    ) : Seq[T]
    {
      def set = HashSet(seq1, SelectEqComparer(selector));
      set.ExceptWith(seq2);
      set
    }
    
    
    #warning not tested
    public SetAdd[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T]
    ) : Seq[T]
    {
       def set = HashSet(seq1);
       set.UnionWith(seq2);
       set
    }
    
    
    #warning not tested
    public SetAddBy[T, K](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
      [NotNull] selector : T -> K 
    ) : Seq[T]
    {
      def set = HashSet(seq1, SelectEqComparer(selector));
      set.UnionWith(seq2);
      set
    }    
    
    
    #warning not tested
    public Intersection[T](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T]
    ) : Seq[T]
    {
       def set = HashSet(seq1);
       set.IntersectWith(seq2);
       set
    }
    
    
    #warning not tested
    public IntersectionBy[T, K](
      [NotNull] this seq1 : Seq[T],
      [NotNull]      seq2 : Seq[T],
      [NotNull] selector : T -> K 
    ) : Seq[T]
    {
      def set = HashSet(seq1, SelectEqComparer(selector));
      set.IntersectWith(seq2);
      set
    }    
    
        
    //---------------
    // Ordered lists
    //---------------
       
    
    #warning not tested
    public Sort[T](
      [NotNull] this seq : Seq[T]
    ) : Seq[T]
    where T : IComparable[T]
    {
      seq.ToArray().SortInplace()
    }
    
    
    #warning not tested
    public Sort[T](
      [NotNull] this seq : Seq[T],
      [NotNull]  compare : IComparer[T] 
    ) : Seq[T]
    {
      seq.ToArray().SortInplace(compare)
    }
    
    
    #warning not tested
    public Sort[T](
      [NotNull] this seq : Seq[T],
      [NotNull]  compare : T * T -> int 
    ) : Seq[T]
    {
      seq.ToArray().SortInplace(compare)
    }
    
    
    #warning not tested
    public SortBy[T, K](
      [NotNull] this seq : Seq[T],
      [NotNull] selector : T -> K 
    ) : Seq[T]
    where K : IComparable[K]
    {
      seq.ToArray().SortInplaceBy(selector)
    }
    
    
    #warning not tested
    public InsertSeq[T](
      [NotNull] this seq : Seq[T],
                    item : T
    ) : Seq[T]
    where T : IComparable[T]
    {
      using(en = seq.GetEnumerator())
      {
        foreach(x when x.CompareTo(item) <= 0 in EnumeratorToEnumerable(en)) 
          yield x;
        yield item;
        foreach(x in EnumeratorToEnumerable(en)) 
          yield x;
      }
    }
    
    [Record]
    private class EnumeratorToEnumerable[T] : IEnumerable[T]
    {
       private _en : IEnumerator[T];
       
       public GetEnumerator() : IEnumerator[T]
       {
         _en
       }
    }
    
    
    #warning not tested
    public InsertBySeq[T, K](
      [NotNull] this seq : Seq[T],
                    item : T,
                selector : T -> K
    ) : Seq[T]
    where K : IComparable[K]
    {
      def key = selector(item); 
      using(en = seq.GetEnumerator())
      {
        foreach(x when selector(x).CompareTo(key) <= 0 in EnumeratorToEnumerable(en)) 
          yield x;
        yield item;
        foreach(x in EnumeratorToEnumerable(en)) 
          yield x;
      }
    }
  }
}
